package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/smallest-string-starting-from-leaf/'>从叶结点开始的最小字符串(Smallest String Starting From Leaf)</a>
 * <p>给定一颗根结点为 root 的二叉树，树中的每一个结点都有一个 [0, 25] 范围内的值，分别代表字母 'a' 到 'z'。</p>
 * <p>返回 按字典序最小 的字符串，该字符串从这棵树的一个叶结点开始，到根结点结束。</p>
 * <p>注：字符串中任何较短的前缀在 字典序上 都是 较小 的：例如，在字典序上 "ab" 比 "aba" 要小。</p>
 * <p>叶结点是指没有子结点的结点。 </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [0,1,2,3,4,3,4]
 *                   a
 *                 /   \
 *                b     c
 *               / \   / \
 *              d   e d   e
 *      输出："dba"
 *
 * 示例 2：
 *      输入：root = [25,1,3,1,3,0,2]
 *                     z
 *                   /   \
 *                  b     d
 *                 / \   / \
 *                b   d a   c
 *      输出："adz"
 *
 * 示例 3：
 *      输入：root = [2,2,1,null,1,0,null,0]
 *      输出："abc"
 * </pre>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 100] 内</li>
 *     <li>1 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/20 17:57
 */
public class LC0988SmallestStringStartingFromLeaf_M {
    static class Solution {

        String ans = "~";

        /**
         * 推荐
         */
        public String smallestFromLeaf(TreeNode root) {
            dfs(root, new StringBuilder());
            return ans;
        }

        private void dfs(TreeNode node, StringBuilder currPath) {
            if (node == null) {
                return;
            }
            currPath.append((char) ('a' + node.val));
            // 如果是叶子节点。找到一条路径
            if (node.left == null && node.right == null) {
                String tempAns = new StringBuilder(currPath).reverse().toString();
                if (tempAns.compareTo(ans) < 0) {
                    ans = tempAns;
                }
                return;
            }
            // 如果左子节点不为null，继续向左子树找叶子节点。查找完后需要剪枝
            if (node.left != null) {
                dfs(node.left, currPath);
                currPath.delete(currPath.length() - 1, currPath.length());
            }
            // 如果右子节点不为null，继续向右子树找叶子节点。查找完后需要剪枝
            if (node.right != null) {
                dfs(node.right, currPath);
                currPath.delete(currPath.length() - 1, currPath.length());
            }
        }

        public String smallestFromLeaf2(TreeNode root) {
            List<String> allPathList = new ArrayList<>();
            // 通过深度优先遍历找到所有可能的路径
            dfs2(root, new StringBuilder(), allPathList);
            // 将所有可能的路径按照升序排序，返回第一个
            Collections.sort(allPathList);
            return allPathList.get(0);
        }

        private void dfs2(TreeNode node, StringBuilder currPath, List<String> allPathList) {
            if (node == null) {
                return;
            }
            currPath.append((char) ('a' + node.val));
            if (node.left == null && node.right == null) {
                allPathList.add(new StringBuilder(currPath).reverse().toString());
            }
            if (node.left != null) {
                dfs2(node.left, currPath, allPathList);
                currPath.delete(currPath.length() - 1, currPath.length());
            }
            if (node.right != null) {
                dfs2(node.right, currPath, allPathList);
                currPath.delete(currPath.length() - 1, currPath.length());
            }
        }

        /**
         * 非递归
         */
        public String smallestFromLeaf3(TreeNode root) {
            if (root == null) {
                return "";
            }
            String ans = "~";
            Queue<TreeNode> nodeQueue = new LinkedList<>();
            nodeQueue.offer(root);
            Queue<StringBuilder> pathQueue = new LinkedList<>();
            pathQueue.offer(new StringBuilder(String.valueOf((char) ('a' + root.val))));
            while (!nodeQueue.isEmpty()) {
                TreeNode currNode = nodeQueue.poll();
                StringBuilder currPath = pathQueue.poll();
                if (currNode.left == null && currNode.right == null) {
                    String tempAns = currPath.reverse().toString();
                    if (tempAns.compareTo(ans) < 0) {
                        ans = tempAns;
                    }
                }
                if (currNode.left != null) {
                    nodeQueue.offer(currNode.left);
                    pathQueue.offer(new StringBuilder(currPath).append((char) ('a' + currNode.left.val)));
                }
                if (currNode.right != null) {
                    nodeQueue.offer(currNode.right);
                    pathQueue.offer(new StringBuilder(currPath).append((char) ('a' + currNode.right.val)));
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(0);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(3);
        root1.left.right = new TreeNode(4);
        root1.right.left = new TreeNode(3);
        root1.right.right = new TreeNode(4);

        TreeNode root2 = new TreeNode(25);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(1);
        root2.left.right = new TreeNode(3);
        root2.right.left = new TreeNode(0);
        root2.right.right = new TreeNode(2);

        TreeNode root3 = new TreeNode(2);
        root3.left = new TreeNode(2);
        root3.right = new TreeNode(1);
        root3.left.right = new TreeNode(1);
        root3.left.right.left = new TreeNode(0);
        root3.right.left = new TreeNode(0);

        Solution solution = new Solution();
        System.out.println(solution.smallestFromLeaf3(root1));
        System.out.println(solution.smallestFromLeaf3(root2));
        System.out.println(solution.smallestFromLeaf3(root3));
    }
}
